COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00016 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a71.tex[106,phy] \today\hfill}

\bigskip
\line{\bf Final Project\hfill}

The game of Chomp begins with a rectangle made of squares, like this:

$$\vcenter{\offinterlineskip
\halign{\hfil#\hfil\xskip&\vrule#&\strut\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#&\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#&\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#\cr
&\omit&1&\omit&2&\omit&3&\omit&4&\omit&5&\omit&6&\omit\cr
\noalign{\smallskip}
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
1&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
2&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
3&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
4&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
}}$$
Each player in turn chomps away any square, and with it all the squares
below and to the right. This can be thought of as covering some of the
squares with the upper left corner of a piece of paper.
$$\vcenter{\offinterlineskip
\halign{\hfil#\hfil\xskip&\vrule#&\strut\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#&\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#&\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#\cr
&\omit&\phantom{1}&\omit&\phantom{2}&\omit&\phantom{3}%
&\omit&\phantom{4}&\omit&\phantom{5}&\omit&\phantom{6}&\omit\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\phantom{1}&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\phantom{2}&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&\cr%&\omit&&\omit&&\omit&\cr
\phantom{3}&&&&&&&\cr%&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&\cr%&\omit&&\omit&&\omit&\cr
&\multispan7\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&\cr%&\omit&&\omit&&\omit&\cr
\phantom{4}&&&&&&&\cr%&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&\cr%&\omit&&\omit&&\omit&\cr
&\multispan7\hrulefill\cr
}}$$


$$\vcenter{\offinterlineskip
\halign{\hfil#\hfil\xskip&\vrule#&\strut\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#&\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#&\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#\cr
&\omit&\phantom{1}&\omit&\phantom{2}&\omit&\phantom{3}%
&\omit&\phantom{4}&\omit&\phantom{5}&\omit&\phantom{6}&\omit\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\phantom{1}&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\phantom{2}&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&\cr%&\omit&&\omit&&\omit&\cr
\phantom{3}&&&&&&&\cr%&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&\cr%&\omit&&\omit&&\omit&\cr
&\multispan7\hrulefill\cr
&height4pt&\omit&\cr%&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
\phantom{4}&&&\cr%&&&&\cr%&&&&&&\cr
&height4pt&\omit&\cr%&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
&\multispan3\hrulefill\cr
}}$$

$$\vcenter{\offinterlineskip
\halign{\hfil#\hfil\xskip&\vrule#&\strut\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#&\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#&\xskip\hfil#\hfil\xskip&\vrule#&%
\xskip\hfil#\hfil\xskip&\vrule#\cr
&\omit&\phantom{1}&\omit&\phantom{2}&\omit&\phantom{3}%
&\omit&\phantom{4}&\omit&\phantom{5}&\omit&\phantom{6}&\omit\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\phantom{1}&&&&&&&&&&&&&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&\multispan{13}\hrulefill\cr
&height4pt&\omit&&\omit&\cr%&\omit&&\omit&&\omit&&\omit&\cr
\phantom{2}&&&&&\cr%&&&&&&&&\cr
&height4pt&\omit&&\omit&\cr%&\omit&&\omit&&\omit&&\omit&\cr
&\multispan5\hrulefill\cr
&height4pt&\omit&&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
\phantom{3}&&&&&\cr%&&\cr%&&&&&&\cr
&height4pt&\omit&&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
&\multispan5\hrulefill\cr
&height4pt&\omit&\cr%&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
\phantom{4}&&&\cr%&&&&\cr%&&&&&&\cr
&height4pt&\omit&\cr%&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
&\multispan3\hrulefill\cr
}}$$
The player who takes the last square loses.

Write a program which plays perfect Chomp, for small rectangles (say,
up to $4\times 5$).

Useful to know:

\disleft 20pt:(1):
Every position is a winner or a loser.

\disleft 20pt:(2):
The position with only one square left is a loser. The one with no squares
left (your opponent has just taken the last one) is a winner.

\disleft 20pt:(3):
If you can move to a postion which is a loser (with your opponent's turn
at hand), your position is a winner.

\disleft 20pt:(4):
If you can't, your position is a loser.

\disleft 20pt:(5):
All $1\times N$ positions, $n≥2$, are winners.

\disleft 20pt:(6):
Positions like this are losers if the height is the same as the width,
otherwise winners:

\figbox 1.5truein:

\line{\qquad\qquad\qquad\qquad Loser\qquad \qquad\qquad\qquad\qquad Winner\hfill}

\bigskip
\disleft 20pt:(7):
Positions symmetric around the diagonal from the upper left can be won
by chomping row~2, column~2---if it's still there.

\figbox 2truein:


A {\sl really\/} good program has the will to fight. In a losing position,
it makes a play that gives the opponent the most ways to make a mistake.

\bigskip\bigskip

\parindent0pt
\copyright 1984 Robert W. Floyd

First draft November 19, 1984

\end


$$\vcenter{\offinterlineskip
\halign{\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\hfil\quad&\vrule#&%
\quad\hfil#\hfil\quad&\vrule#&\quad\hfil#\hfil\quad&\vrule#&%
\quad\hfil#\hfil\quad&\vrule#\qquad\qquad
&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\hfil\quad&\vrule#&%
\quad\hfil#\hfil\quad&\vrule#&\quad\hfil#\hfil\quad&\vrule#&%
\quad\hfil#\hfil\quad&\vrule#&\quad\hfil#\hfil\quad&\vrule#&%
\quad\hfil#\hfil\quad&\vrule#&%
\quad\hfil#\hfil\quad&\vrule#\cr
&\multispan9\hrulefill&\multispan{15}\hrulefill\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit%
&&\omit&\cr
&&\phantom{1}&&\phantom{2}&&\phantom{3}%
&&\phantom{4}&&&\phantom{1}&&\phantom{2}%
&&\phantom{3}&&\phantom{4}&&\phantom{5}%
&&\phantom{6}&&\phantom{7}&\cr
&height4pt&\omit&&\omit&&\omit&&\omit&&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit%
&&\omit&\cr
&\multispan9\hrulefill&\multispan{15}\hrulefill\cr
&height4pt&\omit&\multispan7&\omit&\cr
}}$$
\bye
\phantom{1}&&&&&&&&&&&&&&&&&&&&&&&&\cr
&&\omit&height4pt&\omit&&\omit&&\omit&&&\omit&&\omit&&\omit&&\omit&&\omit%
&&\omit&&\omit&\cr
&&&\multispan7\hrulefill&&&&\multispan{13}\hrulefill\cr
}}$$

\bye
&height4pt&\omit&&\omit&\cr%&\omit&&\omit&&\omit&&\omit&\cr
\phantom{2}&&&&&\cr%&&&&&&&&\cr
&height4pt&\omit&&\omit&\cr%&\omit&&\omit&&\omit&&\omit&\cr
&\multispan5\hrulefill\cr
&height4pt&\omit&&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
\phantom{3}&&&&&\cr%&&\cr%&&&&&&\cr
&height4pt&\omit&&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
&\multispan5\hrulefill\cr
&height4pt&\omit&\cr%&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
\phantom{4}&&&\cr%&&&&\cr%&&&&&&\cr
&height4pt&\omit&\cr%&\omit&\cr%&\omit&\cr%&\omit&&\omit&&\omit&\cr
&\multispan3\hrulefill\cr
}}$$





\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft November 19, 1984

\bye